/**
 * @brief QELIB Hash
 * @copyright Copyright (C) 2024 Wei.Studio
 */



#include "qe_hash.h"
#include "qe_assert.h"
#include "qe_memory.h"
#include "qe_string.h"
#include "qe_macros.h"
#include "qe_log.h"



QELOG_DOMAIN(QELOG_DOMAIN_HASH);



#define HASH_TABLE_MIN_SHIFT 3  /* 1 << 3 == 8 buckets */
#define UNUSED_HASH_VALUE 0
#define TOMBSTONE_HASH_VALUE 1
#define HASH_IS_UNUSED(h_) ((h_) == UNUSED_HASH_VALUE)
#define HASH_IS_TOMBSTONE(h_) ((h_) == TOMBSTONE_HASH_VALUE)
#define HASH_IS_REAL(h_) ((h_) >= 2)



struct qe_hash_table
{
    qe_size      size;
    qe_uint      mod;
    qe_uint      mask;
    qe_uint      num_nodes;
    qe_uint      num_occupied;

    qe_ptr       keys;
    qe_ptr       vals;
    qe_uint     *hashes;

    qe_hash_func       hash_func;
    qe_hash_equal_func key_equal_func;
    qe_destroy_notify  key_destroy_func;
    qe_destroy_notify  val_destroy_func;
};

/* Each table size has an associated prime modulo (the first prime
 * lower than the table size) used to find the initial bucket. Probing
 * then works modulo 2^n. The prime modulo is necessary to get a
 * good distribution with poor hash functions.
 */
static const qe_uint prime_mod[] = 
{
    1,          /* For 1 << 0 */
    2,
    3,
    7,
    13,
    31,
    61,
    127,
    251,
    509,
    1021,
    2039,
    4093,
    8191,
    16381,
    32749,
    65521,      /* For 1 << 16 */
    131071,
    262139,
    524287,
    1048573,
    2097143,
    4194301,
    8388593,
    16777213,
    33554393,
    67108859,
    134217689,
    268435399,
    536870909,
    1073741789,
    2147483647  /* For 1 << 31 */
};

static void set_shift(qe_hashtab *tab, qe_uint shift)
{
    tab->size = 1 << shift;
    tab->mod  = prime_mod[shift];

    /* tab->size is always a power of two, so we can calculate the mask
     * by simply subtracting 1 from it. The leading assertion ensures that
     * we're really dealing with a power of two. */

    qe_assert((tab->size & (tab->size - 1)) == 0);
    tab->mask = tab->size - 1;
}

static qe_uint find_colsest_shift(qe_uint n)
{
    qe_uint i;

    for (i = 0; n; i++)
        n >>= 1;

    return i;
}

static void set_shift_from_size(qe_hashtab *tab, qe_uint size)
{
    qe_uint shift;

    shift = find_colsest_shift(size);
    shift = qe_max(shift, HASH_TABLE_MIN_SHIFT);

    set_shift(tab, shift);
}

static inline qe_ptr realloc_kv(qe_ptr a, qe_uint size)
{
    return qe_realloc(a, size);
}

static void realloc_arrays(qe_hashtab *tab, qe_bool is_a_set)
{
    tab->hashes = qe_realloc(tab->hashes, sizeof(qe_uint) * tab->size);
    tab->keys = realloc_kv(tab->keys, sizeof(qe_ptr) * tab->size);
    qe_debug("realloc hashes and keys");
    if (is_a_set) {
        tab->vals = tab->keys;
    } else {
        tab->vals = realloc_kv(tab->vals, tab->size);
        qe_debug("realloc vals");
    }
}

static inline qe_ptr fetch_kv(qe_ptr a, qe_uint index)
{
    return *(((qe_ptr *) a) + index);
}

static inline void assign_kv(qe_ptr a, qe_uint index, qe_ptr v)
{
    *(((qe_ptr *) a) + index) = v;
}

static inline void ensure_kv_fits(qe_hashtab *tab, qe_ptr key, qe_ptr val)
{
    qe_bool is_a_set = (tab->keys == tab->vals);

    if (is_a_set && key != val) {
        tab->vals = qe_memdup(tab->keys, sizeof (qe_ptr) * tab->size);
    }
}

static inline qe_ptr evict_kv(qe_ptr a, qe_uint index, qe_ptr v)
{
    qe_ptr r = *(((qe_ptr *) a) + index);
    *(((qe_ptr *) a) + index) = v;
    return r;
}

static inline qe_uint hash2index(qe_hashtab *tab, qe_uint hash)
{
    /* Multiply the hash by a small prime before applying the modulo. This
     * prevents the table from becoming densely packed, even with a poor hash
     * function. A densely packed table would have poor performance on
     * workloads with many failed lookups or a high degree of churn. */
    return (hash * 11) % tab->mod;
}

/* When resizing the table in place, we use a temporary bit array to keep
 * track of which entries have been assigned a proper location in the new
 * table layout.
 *
 * Each bit corresponds to a bucket. A bit is set if an entry was assigned
 * its corresponding location during the resize and thus should not be
 * evicted. The array starts out cleared to zero. */

static inline qe_bool get_status_bit(const qe_u32 *bitmap, qe_uint index)
{
    return (bitmap[index / 32] >> (index % 32)) & 1;
}

static inline void set_status_bit(qe_u32 *bitmap, qe_uint index)
{
    bitmap[index / 32] |= 1U << (index % 32);
}

#define DEFINE_RESIZE_FUNC(fname) \
static void fname(qe_hashtab *tab, qe_uint old_size, qe_u32 *reallocated_buckets_bitmap) \
{                                                                           \
    qe_uint i;                                                              \
                                                                            \
    for (i=0; i<old_size; i++) {                                            \
                                                                            \
        qe_uint node_hash = tab->hashes[i];                                 \
        qe_ptr key, val;                                                    \
                                                                            \
        if (!HASH_IS_REAL(node_hash)) {                                     \
            /* Clear tombstones */                                          \
            tab->hashes[i] = UNUSED_HASH_VALUE;                             \
            continue;                                                       \
        }                                                                   \
                                                                            \
        /* Skip entries relocated through eviction */                       \
        if (get_status_bit(reallocated_buckets_bitmap, i))                  \
            continue;                                                       \
                                                                            \
        tab->hashes[i] = UNUSED_HASH_VALUE;                                 \
        EVICT_KEYVAL(tab, i, QE_NULL, QE_NULL, key, val);                   \
                                                                            \
        for (;;) {                                                          \
            qe_uint hash_val;                                               \
            qe_uint replaced_hash;                                          \
            qe_uint step = 0;                                               \
            hash_val = hash2index(tab, node_hash);                          \
            while (get_status_bit(reallocated_buckets_bitmap, hash_val)) {  \
                step++;                                                     \
                hash_val += step;                                           \
                hash_val &= tab->mask;                                      \
            }                                                               \
            set_status_bit(reallocated_buckets_bitmap, hash_val);           \
            replaced_hash = tab->hashes[hash_val];                          \
            tab->hashes[hash_val] = node_hash;                              \
            if (!HASH_IS_REAL(replaced_hash)) {                             \
                ASSIGN_KEYVAL(tab, hash_val, key, val);                     \
                break;                                                      \
            }                                                               \
            node_hash = replaced_hash;                                      \
            EVICT_KEYVAL(tab, hash_val, key, val, key, val);                \
        }                                                                   \
    }                                                                       \
}

#define ASSIGN_KEYVAL(ht, index, key, val) do { \
    assign_kv((ht)->keys, (index), (key));      \
    assign_kv((ht)->vals, (index), (val));      \
} while(0)

#define EVICT_KEYVAL(ht, index, key, val, outkey, outval) do {  \
    (outkey) = evict_kv((ht)->keys, (index), (key));            \
    (outval) = evict_kv((ht)->vals, (index), (val));            \
} while(0)

DEFINE_RESIZE_FUNC(resize_map)

#undef ASSIGN_KEYVAL
#undef EVICT_KEYVAL

#define ASSIGN_KEYVAL(ht, index, key, val) do { \
    assign_kv((ht)->keys, (index), (key));      \
} while(0)

#define EVICT_KEYVAL(ht, index, key, val, outkey, outval) do {  \
    (outkey) = evict_kv((ht)->keys, (index), (key));            \
} while(0)

DEFINE_RESIZE_FUNC(resize_set)

#undef ASSIGN_KEYVAL
#undef EVICT_KEYVAL

static void hashtab_resize(qe_hashtab *tab)
{
    qe_u32 *reallocated_buckets_bitmap;
    qe_size old_size;
    qe_bool is_a_set;

    old_size = tab->size;
    is_a_set = tab->keys == tab->vals;

    set_shift_from_size(tab, tab->num_nodes * 1.333);
    qe_debug("resize size:%d mod:%d mask:0x%x", tab->size, tab->mod, tab->mask);

    if (tab->size > old_size) {
        qe_debug("resize up");
        realloc_arrays(tab, is_a_set);
        qe_memset(&tab->hashes[old_size], 0, (tab->size - old_size) * sizeof (qe_uint));
        reallocated_buckets_bitmap = (qe_u32 *)qe_malloc(sizeof(qe_uint) * (tab->size + 31) / 32);
    } else {
        reallocated_buckets_bitmap = (qe_u32 *)qe_malloc(sizeof(qe_uint) * (old_size + 31) / 32);
    }

    if (is_a_set)
        resize_set(tab, old_size, reallocated_buckets_bitmap);
    else
        resize_map(tab, old_size, reallocated_buckets_bitmap);
    
    qe_free(reallocated_buckets_bitmap);

    if (tab->size < old_size) {
        qe_debug("resize down");
        realloc_arrays(tab, is_a_set);
    }

    tab->num_occupied = tab->num_nodes;
}

static inline void maybe_resize(qe_hashtab *tab)
{
    qe_size num_occupied = tab->num_occupied;
    qe_size size = tab->size;

    if ((size > tab->num_nodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
        (size <= num_occupied + (num_occupied / 16))) {
        hashtab_resize(tab);
    }
}

static qe_bool insert_node(qe_hashtab *tab,
                             qe_uint node_index,
                             qe_uint key_hash,
                             qe_ptr new_key,
                             qe_ptr new_val,
                             qe_bool keep_new_key,
                             qe_bool reusing_key)
{
    qe_bool already_exists;
    qe_uint old_hash;
    qe_ptr key_to_free = QE_NULL;
    qe_ptr key_to_keep = QE_NULL;
    qe_ptr val_to_free = QE_NULL;

    old_hash = tab->hashes[node_index];
    already_exists = HASH_IS_REAL(old_hash);

    if (already_exists) {
        val_to_free = fetch_kv(tab->vals, node_index);
        if (keep_new_key) {
            key_to_free = fetch_kv(tab->keys, node_index);
            key_to_keep = new_key;
        } else {
            key_to_free = new_key;
            key_to_keep = fetch_kv(tab->keys, node_index);
        }
    } else {
        tab->hashes[node_index] = key_hash;
        key_to_keep = new_key;
    }

    ensure_kv_fits(tab, key_to_keep, new_val);
    assign_kv(tab->keys, node_index, key_to_keep);
    assign_kv(tab->vals, node_index, new_val);

    if (!already_exists) {
        tab->num_nodes++;
        if (HASH_IS_UNUSED(old_hash)) {
            tab->num_occupied++;
            maybe_resize(tab);
        }
    } else {
        if (tab->key_destroy_func && !reusing_key) {
            tab->key_destroy_func(key_to_free);
        }
        if (tab->val_destroy_func) {
            tab->val_destroy_func(val_to_free);
        }
    }

    qe_info("insert node[%d:%u] k:%p v:%p", node_index, key_hash, new_key, new_val);
    return !already_exists;
}

static inline qe_uint lookup_node(qe_hashtab *tab, qe_const_ptr key, qe_uint *hash_return)
{
    qe_uint node_index;
    qe_uint node_hash;
    qe_uint hash_value;
    qe_uint first_tombstone = 0;
    qe_bool have_tombstone = qe_false;
    qe_uint step = 0;

    hash_value = tab->hash_func(key);
    if (qe_unlikely(!HASH_IS_REAL(hash_value)))
    hash_value = 2;

    *hash_return = hash_value;

    node_index = hash2index(tab, hash_value);
    node_hash = tab->hashes[node_index];

    while (!HASH_IS_UNUSED (node_hash)) {
        /* We first check if our full hash values
        * are equal so we can avoid calling the full-blown
        * key equality function in most cases.
        */
        if (node_hash == hash_value) {
            qe_ptr node_key = fetch_kv(tab->keys, node_index);

            if (tab->key_equal_func) {
                if (tab->key_equal_func(node_key, key))
                    return node_index;
            } else if (node_key == key) {
                return node_index;
            }
        } else if (HASH_IS_TOMBSTONE (node_hash) && !have_tombstone) {
            first_tombstone = node_index;
            have_tombstone = qe_true;
        }

        step++;
        node_index += step;
        node_index &= tab->mask;
        node_hash = tab->hashes[node_index];
    }

    if (have_tombstone)
        return first_tombstone;

    return node_index;
}

static void remove_node(qe_hashtab *tab, int i, qe_bool notify)
{
    qe_ptr key;
    qe_ptr value;

    key = fetch_kv(tab->keys, i);
    value = fetch_kv(tab->vals, i);

    /* Erect tombstone */
    tab->hashes[i] = TOMBSTONE_HASH_VALUE;

    /* Be GC friendly */
    assign_kv(tab->keys, i, QE_NULL);
    assign_kv(tab->vals, i, QE_NULL);

    qe_assert(tab->num_nodes > 0);
    tab->num_nodes--;

    if (notify && tab->key_destroy_func)
        tab->key_destroy_func(key);

    if (notify && tab->val_destroy_func)
        tab->val_destroy_func(value);
}

static void setup_storage(qe_hashtab *tab)
{
    qe_bool small = qe_false;

    /* We want to use small arrays only if:
     *   - we are running on a system where that makes sense (64 bit); and
     *   - we are not running under valgrind.
     */

    set_shift(tab, HASH_TABLE_MIN_SHIFT);

    tab->keys   = realloc_kv(QE_NULL, sizeof(qe_ptr)*tab->size);
    tab->vals   = tab->keys;
    tab->hashes = qe_malloc(sizeof(qe_uint)*tab->size);
    qe_memset(tab->hashes, 0x0, sizeof(qe_uint)*tab->size);
    qe_debug("setup storage");
}

static void remove_all_nodes(qe_hashtab *tab, qe_bool notify, qe_bool destruction)
{
    int i;
    qe_ptr    key;
    qe_ptr    val;
    qe_uint   old_size;
    qe_ptr   old_keys;
    qe_ptr   old_values;
    qe_uint  *old_hashes;
    qe_bool old_have_big_keys;
    qe_bool old_have_big_values;

    /* If the hash table is already empty, there is nothing to be done. */
    if (tab->num_nodes == 0)
        return;

    tab->num_nodes = 0;
    tab->num_occupied = 0;

    /* Easy case: no callbacks, so we just zero out the arrays */
    if (!notify ||
        (tab->key_destroy_func == QE_NULL &&
        tab->val_destroy_func == QE_NULL)) {
        if (!destruction) {
            qe_debug("no notify, only set zero");
            qe_memset(tab->hashes, 0, tab->size * sizeof(qe_uint));
            qe_memset(tab->keys, 0, tab->size * sizeof(qe_ptr));
            qe_memset(tab->vals, 0, tab->size * sizeof(qe_ptr));
        }

        return;
    }

    /* Hard case: we need to do user callbacks.  There are two
     * possibilities here:
     *
     *   1) there are no outstanding references on the table and therefore
     *   nobody should be calling into it again (destroying == true)
     *
     *   2) there are outstanding references, and there may be future
     *   calls into the table, either after we return, or from the destroy
     *   notifies that we're about to do (destroying == false)
     *
     * We handle both cases by taking the current state of the table into
     * local variables and replacing it with something else: in the "no
     * outstanding references" cases we replace it with a bunch of
     * null/zero values so that any access to the table will fail.  In the
     * "may receive future calls" case, we reinitialise the struct to
     * appear like a newly-created empty table.
     *
     * In both cases, we take over the references for the current state,
     * freeing them below.
     */
    old_size = tab->size;
    old_keys   = tab->keys;
    old_values = tab->vals;
    old_hashes = tab->hashes;

    if (!destruction)
        /* Any accesses will see an empty table */
        setup_storage(tab);
    else
        /* Will cause a quick crash on any attempted access */
        tab->size = tab->mod = tab->mask = 0;

    /* Now do the actual destroy notifies */
    for (i = 0; i < old_size; i++) {
        if (HASH_IS_REAL (old_hashes[i])) {
            key = fetch_kv(old_keys, i);
            val = fetch_kv(old_values, i);

            old_hashes[i] = UNUSED_HASH_VALUE;

            assign_kv(old_keys, i, QE_NULL);
            assign_kv(old_values, i, QE_NULL);

            if (tab->key_destroy_func != QE_NULL) {
                qe_debug("destroy k:%p", key);
                tab->key_destroy_func(key);
            }

            if (tab->val_destroy_func != QE_NULL) {
                qe_debug("destroy v:%p", val);
                tab->val_destroy_func(val);
            }
        }
    }

    /* Destroy old storage space. */
    if (old_keys != old_values) {
        qe_free(old_values);
    }

    qe_free(old_keys);
    qe_free(old_hashes);
}


/**
 * @brief Create a @qe_hashtab like qe_hashtab_new(), and allows to 
 * specify functions to free key and values.
 * 
 * @param hash_func : a function to create a hash value from a key
 * @param equal_func : a function to check two keys for equality
 * @param key_destroy_func : a memory free function for key, or null
 *      if you don't want to supply such a function.
 * @param val_destroy_func : a memory free function for value, or null
 *      if you don't want to supply such a function.
 * 
 * @return #qe_hashtab
 */
qe_hashtab *qe_hashtab_new_full(qe_hash_func       hash_func, 
                                qe_hash_equal_func equal_func, 
                                qe_destroy_notify  key_destroy_func,
                                qe_destroy_notify  val_destroy_func)
{
    qe_hashtab *tab;

    tab = qe_malloc(sizeof(qe_hashtab));
    if (!tab) {
        qe_error("alloc mem for hashtab error");
        return QE_NULL;
    }

    tab->num_nodes        = 0;
    tab->num_occupied     = 0;
    tab->hash_func        = hash_func ? hash_func : qe_direct_hash;
    tab->key_equal_func   = equal_func ? equal_func : qe_direct_equal;
    tab->key_destroy_func = key_destroy_func;
    tab->val_destroy_func = val_destroy_func;

    setup_storage(tab);

    qe_info("new hashtab");

    return tab;
}

/**
 * @brief Create a new #qe_hashtab
 * 
 * @param hash_func : a function to create a hash value from a key
 * @param equal_func : a function to check two keys for equality
 * 
 * @note 
 * Hash values returned by @hash_func are used to determine where keys
 * are stored within the #qe_hashtab data structure. There are some 
 * prepared hash functions, like qe_direct_hash(),
 * qe_int_hash(), qe_int64_hash(), qe_double_hash(), qe_str_hash().
 * If @hash_func is null, qe_direct_hash() is used.
 * 
 * @equal_func is used when looking up keys in the hash table. There are 
 * some prepared equal functions, like qe_direct_equal(), qe_int_equal(),
 * qe_int64_equal(), qe_double_equal(), qe_str_equal(). If @equal_func is
 * null, qe_direct_equal() is used.
 * 
 * @return a new #qe_hashtab
 */
qe_hashtab *qe_hashtab_new(qe_hash_func hash_func, qe_hash_equal_func equal_func)
{
    return qe_hashtab_new_full(hash_func, equal_func, QE_NULL, QE_NULL);
}

/**
 * @brief Atomically decrements the reference count of @tab by one.
 * If the reference count drops to 0, all keys and values will be
 * destroyed, and all memory allocated by the hash table is released.
 * This function is MT-safe and may be called from any thread.
 * 
 * @param tab: (transfer full): a valid #qe_hashtab
 *
 */
void qe_hashtab_unref(qe_hashtab *tab)
{
    if (!tab)
        return;

    remove_all_nodes(tab, qe_true, qe_true);
    if (tab->keys != tab->vals)
        qe_free(tab->vals);
    qe_free(tab->keys);
    qe_free(tab->hashes);
    qe_free(tab);
}

/**
 * @brief Removes all keys and their associated values from a #qe_hashtab.
 * 
 * @param tab: a #qe_hashtab
 */
void qe_hashtab_remove_all(qe_hashtab *tab)
{
    if (!tab) {
        qe_error("hashtab null");
        return;
    }

    remove_all_nodes(tab, qe_true, qe_false);
    maybe_resize(tab);
}


/**
 * @brief Destroys all keys and values in the #qe_hashtab and decrements its
 * reference count by 1. If keys and/or values are dynamically allocated,
 * you should either free them first or create the #qe_hashtab with destroy
 * notifiers using qe_hashtab_new_full(). In the latter case the destroy
 * functions you supplied will be called on all keys and values during the
 * destruction phase.
 * 
 * @param tab: a #qe_hashtab
 */
void qe_hashtab_destroy(qe_hashtab *tab)
{
    if (!tab)
        return;

    qe_hashtab_remove_all(tab);
    qe_hashtab_unref(tab);
}

/**
 * @brief Looks up a key in a #qe_hashtab. Note that this function cannot
 * distinguish between a key that is not present and one which is present
 * and has the value %NULL. If you need this distinction, use
 * qe_hashtab_lookup_extended().
 *
 * @param tab: a #qe_hashtab
 * @param key: the key to look up
 *
 * @return (nullable): the associated value, or %NULL if the key is not found
 */
qe_ptr qe_hashtab_lookup(qe_hashtab *tab, qe_const_ptr key)
{
    qe_uint node_index;
    qe_uint node_hash;

    if (!tab) {
        qe_error("hashtab null");
        return QE_NULL;
    }

    node_index = lookup_node(tab, key, &node_hash);
    qe_info("lookup node[%d:%u]", node_index, node_hash);
    return HASH_IS_REAL(tab->hashes[node_index])
        ? fetch_kv(tab->vals, node_index)
        : QE_NULL;
}

/**
 * @brief Looks up a key in the #qe_hashtab, returning the original key and the
 * associated value and a #gboolean which is %TRUE if the key was found. This
 * is useful if you need to free the memory allocated for the original key,
 * for example before calling qe_hashtab_remove().
 * 
 * @param tab: a #qe_hashtab
 * @param lookup_key: the key to look up
 * @param orig_key: (out) (optional): return location for the original key
 * @param value: (out) (optional) (nullable): return location for the value 
 * associated with the key
 *
 * You can actually pass %NULL for @lookup_key to test
 * whether the %NULL key exists, provided the hash and equal functions
 * of @tab are %NULL-safe.
 *
 * @return %TRUE if the key was found in the #qe_hashtab
 */
qe_bool qe_hashtab_lookup_extended(qe_hashtab *tab, qe_const_ptr lookup_key,
    qe_ptr *orig_key, qe_ptr *value)
{
    qe_uint node_index;
    qe_uint node_hash;

    if (!tab) {
        qe_error("hashtab null");
        return qe_false;
    }

    node_index = lookup_node(tab, lookup_key, &node_hash);

    if (!HASH_IS_REAL(tab->hashes[node_index])) {
        if (orig_key != QE_NULL)
            *orig_key = QE_NULL;
        if (value != QE_NULL)
            *value = QE_NULL;

        return qe_false;
    }

    if (orig_key)
        *orig_key = fetch_kv(tab->keys, node_index);

    if (value)
        *value = fetch_kv(tab->vals, node_index);

    return qe_true;
}

/**
 * @brief Implements the common logic for the qe_hashtab_insert() and
 * qe_hashtab_replace() functions.
 * 
 * @param tab: our #qe_hashtab
 * @param key: the key to insert
 * @param val: the value to insert
 * @keep_new_key: if true and this key already exists in the table
 * then call the destroy notify function on the old key. If false
 * then call the destroy notify function on the new key.
 *
 * Do a lookup of @key. If it is found, replace it with the new
 * @value (and perhaps the new @key). If it is not found, create
 * a new node.
 *
 * @return true if the key did not exist yet
 */
static qe_bool insert_internal(qe_hashtab *tab, 
                                 qe_ptr      key,
                                 qe_ptr      val, 
                                 qe_bool   keep_new_key)
{
    qe_uint key_hash;
    qe_uint node_index;

    if (!tab) {
        qe_error("hashtab null");
        return qe_false;
    }

    node_index = lookup_node(tab, key, &key_hash);

    return insert_node(tab, node_index, key_hash, key, val, keep_new_key, qe_false);
}

static qe_bool remove_internal(qe_hashtab  *tab, 
                                 qe_const_ptr key,
                                 qe_bool    notify)
{
    qe_uint node_index;
    qe_uint node_hash;

    if (!tab) {
        qe_error("hashtab null");
        return qe_false;
    }
    
    node_index = lookup_node(tab, key, &node_hash);

    if (!HASH_IS_REAL(tab->hashes[node_index])) {
        qe_warning("key %p is not a real hash %d:%u", node_index, tab->hashes[node_index]);
        return qe_false;
    }

    remove_node(tab, node_index, notify);
    maybe_resize(tab);

    return qe_true;
}

/**
 * @brief Inserts a new key and value into a #qe_hashtab.
 * 
 * @param tab: a #qe_hashtab
 * @param key: a key to insert
 * @param val: the value to associate with the key
 *
 * If the key already exists in the #qe_hashtab its current
 * value is replaced with the new value. If you supplied a
 * @value_destroy_func when creating the #qe_hashtab, the old
 * value is freed using that function. If you supplied a
 * @key_destroy_func when creating the #qe_hashtab, the passed
 * key is freed using that function.
 *
 * @return true if the key did not exist yet
 */
qe_bool qe_hashtab_insert(qe_hashtab *tab, qe_ptr key, qe_ptr val)
{
    return insert_internal(tab, key, val, qe_false);
}

/**
 * @brief Inserts a new key and value into a #qe_hashtab similar to
 * qe_hashtab_insert().
 * 
 * @param tab: a #qe_hashtab
 * @param key: a key to insert
 * @param val: the value to associate with the key
 *
 * The difference is that if the key already exists in the #qe_hashtab, 
 * it gets replaced by the new key. If you supplied a @value_destroy_func 
 * when creating the #qe_hashtab, the old value is freed using that function.
 * If you supplied a @key_destroy_func when creating the #qe_hashtab, the 
 * old key is freed using that function.
 *
 * @return true if the key did not exist yet
 */
qe_bool qe_hashtab_replace(qe_hashtab *tab, qe_ptr key, qe_ptr val)
{
    return insert_internal(tab, key, val, qe_true);
}

/**
 * @brief This is a convenience function for using a #qe_hashtab as a set.  
 * It is equivalent to calling qe_hashtab_replace() with @key as both the
 * key and the value.
 * 
 * @param tab: a #qe_hashtab
 * @param key: (transfer full): a key to insert
 *
 * In particular, this means that if @key already exists in the hash table, then
 * the old copy of @key in the hash table is freed and @key replaces it in the
 * table.
 *
 * When a hash table only ever contains keys that have themselves as the
 * corresponding value it is able to be stored more efficiently.  See
 * the discussion in the section description.
 *
 * @return true if the key did not exist yet
 *
 */
qe_bool qe_hashtab_add(qe_hashtab *tab, qe_ptr key)
{
    return insert_internal(tab, key, key, qe_true);
}

/**
 * @brief Remove a key and it's value from #qe_hashtab
 * 
 * @param tab : a #qe_hashtab
 * @param key : the key to remove
 * @return true if key was found and removed from the table
 */
qe_bool qe_hashtab_remove(qe_hashtab *tab, qe_const_ptr key)
{
    return remove_internal(tab, key, qe_true);
}

/**
 * @brief Remove a key and it's value without calling destroy function
 * 
 * @param tab : a #qe_hashtab
 * @param key : the key to remove
 * 
 * @return true if key was found and removed from the table
 */
qe_bool qe_hashtab_steal(qe_hashtab *tab, qe_const_ptr key)
{
    return remove_internal(tab, key, qe_false);
}

/**
 * @brief Iterates over every node in the table, calling @func with the key
 * and value of the node (and @user). If @func returns true the
 * node is removed from the table.
 * 
 * @param tab: a #qe_hashtab
 * @param func: the user's callback function
 * @param user: data for @func
 * @notify: true if the destroy notify handlers are to be called
 *
 * Implements the common logic for qe_hashtab_foreach_remove()
 * and qe_hashtab_foreach_steal().
 *
 * Iterates over every node in the table, calling @func with the key
 * and value of the node (and @user). If @func returns true the
 * node is removed from the table.
 *
 * If @notify is true then the destroy notify handlers will be called
 * for each removed node.
 */
static qe_uint foreach_remove_or_steal(qe_hashtab *tab,
    qe_hash_r_func func, qe_ptr user, qe_bool notify)
{
    qe_uint deleted = 0;
    qe_int i;

    for (i=0; i<tab->size; i++) {
        qe_uint node_hash = tab->hashes[i];
        qe_ptr node_key = fetch_kv(tab->keys, i);
        qe_ptr node_value = fetch_kv(tab->vals, i);

        if (HASH_IS_REAL(node_hash) &&
            (* func) (node_key, node_value, user)) {
            remove_node(tab, i, notify);
            deleted++;
        }
    }

    maybe_resize(tab);

    return deleted;
}

/**
 * @brief Calls the given function for each key/value pair in the
 * #qe_hashtab.
 * 
 * @param tab: a #qe_hashtab
 * @param func: (scope call): the function to call for each key/value pair
 * @param user: user data to pass to the function
 *
 *  If the function returns true, then the key/value
 * pair is removed from the #qe_hashtab. If you supplied key or
 * value destroy functions when creating the #qe_hashtab, they are
 * used to free the memory allocated for the removed keys and values.
 *
 * See #qe_hashtab_iter for an alternative way to loop over the
 * key/value pairs in the hash table.
 *
 * @return the number of key/value pairs removed
 */
qe_uint qe_hashtab_foreach_remove(qe_hashtab *tab, qe_hash_r_func func, qe_ptr user)
{
    if (!tab || !func) {
        qe_error("hashtab or func null");
        return 0;
    }

  return foreach_remove_or_steal(tab, func, user, qe_true);
}

/**
 * @brief Calls the given function for each key/value pair in the
 * #qe_hashtab.
 * 
 * @param tab: a #qe_hashtab
 * @param func: (scope call): the function to call for each key/value pair
 * @param user: user data to pass to the function
 *
 * If the function returns true, then the key/value pair is removed 
 * from the #qe_hashtab, but no key or value destroy functions are 
 * called.
 *
 * See #qe_hashtab_iter for an alternative way to loop over the
 * key/value pairs in the hash table.
 *
 * @return the number of key/value pairs removed.
 */
qe_uint qe_hashtab_foreach_steal(qe_hashtab *tab, qe_hash_r_func func, qe_ptr user)
{
    if (!tab || !func) {
        qe_error("hashtab or func null");
        return 0;
    }

  return foreach_remove_or_steal(tab, func, user, qe_false);
}

/**
 * @brief Calls the given function for each of the key/value pairs in the
 * #qe_hashtab.
 * 
 * @param tab: a #qe_hashtab
 * @param func: (scope call): the function to call for each key/value pair
 * @param user: user data to pass to the function
 *
 * The function is passed the key and value of each pair, and the given 
 * @user parameter.  The hash table may notbe modified while iterating 
 * over it (you can't add/remove items). To remove all items matching a 
 * predicate, use qe_hashtab_foreach_remove().
 *
 * The order in which qe_hashtab_foreach() iterates over the keys/values in
 * the hash table is not defined.
 *
 * See qe_hashtab_find() for performance caveats for linear
 * order searches in contrast to qe_hashtab_lookup().
 */
void qe_hashtab_foreach(qe_hashtab *tab, qe_hash_r_func func, qe_ptr user)
{
    qe_int i;

    if (!tab) {
        qe_error("hashtab null");
        return;
    }
    
    if (!func) {
        qe_error("func null");
        return;
    }

    for (i=0; i<tab->size; i++) {
        qe_uint node_hash = tab->hashes[i];
        qe_ptr node_key = fetch_kv(tab->keys, i);
        qe_ptr node_val = fetch_kv(tab->vals, i);
        if (HASH_IS_REAL(node_hash))
            (*func)(node_key, node_val, user);
    }
}

/**
 * @brief Calls the given function for key/value pairs in the @qe_hashtab
 * until @predicate return true;
 * 
 * @param tab: a #qe_hashtab
 * @param predicate: (scope call): function to test the key/value pairs for a certain property
 * @param user: user data to pass to the function
 * 
 * The function is passed the key and value of each pair, and the given 
 * @user parameter. The hash table may not be modified while iterating 
 * over it (you can't add/remove items).
 *
 * Note, that hash tables are really only optimized for forward
 * lookups, i.e. qe_hashtab_lookup(). So code that frequently issues
 * qe_hashtab_find() or qe_hashtab_foreach() (e.g. in the order of
 * once per every entry in a hash table) should probably be reworked
 * to use additional or different data structures for reverse lookups
 * (keep in mind that an O(n) find/foreach operation issued for all n
 * values in a hash table ends up needing O(n*n) operations).
 * 
 * @return (nullable): The value of the first key/value pair is returned,
 *     for which @predicate evaluates to true. If no pair with the
 *     requested property is found, null is returned.
 */
qe_ptr qe_hashtab_find(qe_hashtab *tab, qe_hash_r_func predicate, qe_ptr user)
{
    qe_int i;
    qe_bool match;

    if (!tab) {
        qe_error("hashtab null");
        return QE_NULL;
    }
    
    if (!predicate) {
        qe_error("predicate null");
        return QE_NULL;
    }

    match = qe_false;

    for (i=0; i<tab->size; i++) {
        qe_uint node_hash = tab->hashes[i];
        qe_ptr node_key   = fetch_kv(tab->keys, i);
        qe_ptr node_val   = fetch_kv(tab->vals, i);
        if (HASH_IS_REAL(node_hash))
            match = predicate(node_key, node_val, user);
        if (match) {
            qe_info("find v:%p", node_val);
            return node_val;
        }
    }

    return QE_NULL;
}

qe_uint qe_hashtab_size(qe_hashtab *tab)
{
    if (!tab) {
        qe_error("hashtab null");
        return 0;
    }

    return tab->num_nodes;
}

/* 
 * Hash functions.
 * ================
 */

/**
 * @brief Compares two strings for byte-by-byte equality and returns true
 * 
 * @param v1: (not nullable) a key
 * @param v2: (not nullable) a key to compare with @v1
 *
 * if they are equal. It can be passed to qe_hashtab_new() as the
 * @key_equal_func parameter, when using non-%NULL strings as keys in a
 * #qe_hashtab.
 *
 * This function is typically used for hash table comparisons, but can be used
 * for general purpose comparisons of non-%NULL strings.
 *
 * @return true if the two keys match
 */
qe_bool qe_str_equal(qe_const_ptr v1, qe_const_ptr v2)
{
    const char *string1 = v1;
    const char *string2 = v2;

    return qe_strcmp(string1, string2) == 0;
}

/**
 * @brief Convert a string to a hash value
 * 
 * @param v: string key
 * 
 * This function implements the widely used "djb" hash apparently
 * posted by Daniel Bernstein to comp.lang.c some time ago.  The 32
 * bit unsigned hash value starts at 5381 and for each byte 'c' in
 * the string, is updated: `hash = hash * 33 + c`. This function
 * uses the signed value of each byte.
 * 
 * It can be passed to qe_hashtab_new() as the @hash_func parameter,
 * when using non-%NULL strings as keys in a #qe_hashtab.
 * 
 * @note Note that this function may not be a perfect fit for all use cases.
 * For example, it produces some hash collisions with strings as short
 * as 2.
 * 
 * @return a hash value corresponding to the key
 */
qe_uint qe_str_hash(qe_const_ptr v)
{
    const signed char *p;
    qe_u32 h = 5381;

    for (p=v; *p!='\0'; p++)
        h = (h << 5) + h + *p;

    return h;
}

/**
 * @brief Convert a pointer to a hash value
 * 
 * It can be passed to qe_hashtab_new() as the @hash_func parameter,
 * when using opaque pointers compared by pointer value as keys in a
 * #qe_hashtab.
 * 
 * This hash function is also appropriate for keys that are integers
 * stored in pointers.
 * 
 * @return a hash value corresponding to the key.
 */
qe_uint qe_direct_hash(qe_const_ptr v)
{
    return (qe_ubase)v;
}

/** 
 * @brief Compares two arguments and returns true if they are equal.
 * 
 * @param v1 : (nullable) a key
 * @param v2 : (nullable) a key to compare with @v1
 * 
 * It can be passed to qe_hashtab_new() as the @key_equal_func
 * parameter, when using opaque pointers compared by pointer value as
 * keys in a #qe_hashtab.
 * 
 * @return true if the two keys match.
 */
qe_bool qe_direct_equal(qe_const_ptr v1, qe_const_ptr v2)
{
    return v1 == v2;
}

/**
 * @brief Compares the two #qe_int values being pointed to and returns
 * true if they are equal.
 * 
 * @param v1: (not nullable) a pointer to a #qe_int key
 * @param v2: (not nullable) a pointer to a #qe_int key to compare with @v1
 * 
 * It can be passed to qe_hashtab_new() as the @key_equal_func
 * parameter, when using non-%NULL pointers to integers as keys in a
 * #qe_hashtab.
 * 
 * @return true if the two keys match.
 */
qe_bool qe_int_equal(qe_const_ptr v1, qe_const_ptr v2)
{
    return *((const qe_int*)v1) == *((const qe_int*)v2);
}

/**
 * @brief Converts a pointer to a #qe_int to a hash value.
 * 
 * @param v : (not nullable) a pointer to a #qe_int key
 *
 * It can be passed to qe_hashtab_new() as the @hash_func parameter,
 * when using non-%NULL pointers to integer values as keys in a #qe_hashtab.
 *
 * @note Note that this function acts on pointers to #qe_int, not on #qe_int
 * directly: if your hash table's keys are of the form
 * `(qe_ptr)n`, use qe_direct_hash() instead.
 *
 * @return a hash value corresponding to the key.
 */
qe_uint qe_int_hash(qe_const_ptr v)
{
    return *(const qe_int*) v;
}

/**
 * @brief Compares the two #qe_uint values being pointed to and returns
 * true if they are equal.
 * 
 * @param v1: (not nullable) a pointer to a #qe_uint key
 * @param v2: (not nullable) a pointer to a #qe_uint key to compare with @v1
 *
 * It can be passed to qe_hashtab_new() as the @key_equal_func
 * parameter, when using non-%NULL pointers to integers as keys in a
 * #qe_hashtab.
 *
 * @note Note that this function acts on pointers to #qe_uint, not on #qe_uint
 * directly: if your hash table's keys are of the form
 * `(qe_ptr)n`, use qe_direct_equal() instead.
 *
 * @return true if the two keys match.
 */
qe_bool qe_uint_equal(qe_const_ptr v1, qe_const_ptr v2)
{
    return *((const qe_uint *) v1) == *((const qe_uint *) v2);
}

/**
 * @brief Converts a pointer to a #qe_uint to a hash value
 * 
 * @param v: (not nullable) a pointer to a #qe_uint key
 *
 * It can be passed to qe_hashtab_new() as the @hash_func parameter,
 * when using non-%NULL pointers to integer values as keys in a #qe_hashtab.
 *
 * @note Note that this function acts on pointers to #qe_uint, not on #qe_uint
 * directly: if your hash table's keys are of the form
 * `(qe_ptr)n`, use qe_direct_hash() instead.
 *
 * @return a hash value corresponding to the key.
 */
qe_uint qe_uint_hash(qe_const_ptr v)
{
    return *(const qe_uint *) v;
}

/**
 * @brief Compares the two #gint64 values being pointed to and returns
 * true if they are equal.
 * 
 * @param v1: (not nullable) a pointer to a #qe_s64 key
 * @param v2: (not nullable) a pointer to a #qe_s64 key to compare with @v1
 *
 * It can be passed to qe_hashtab_new() as the @key_equal_func
 * parameter, when using non-%NULL pointers to 64-bit integers as keys in a
 * #qe_hashtab.
 *
 * @return true if the two keys match.
 */
qe_bool qe_int64_equal(qe_const_ptr v1, qe_const_ptr v2)
{
    return *((const qe_s64*) v1) == *((const qe_s64*) v2);
}

/**
 * @brief Converts a pointer to a #gint64 to a hash value.
 * 
 * @param v: (not nullable) a pointer to a #qe_s64 key
 *
 * It can be passed to qe_hashtab_new() as the @hash_func parameter,
 * when using non-%NULL pointers to 64-bit integer values as keys in a
 * #qe_hashtab.
 *
 * @return a hash value corresponding to the key.
 */
qe_uint qe_int64_hash(qe_const_ptr v)
{
  const qe_u64 *bits = v;

  return (qe_uint) ((*bits >> 32) ^ (*bits & 0xffffffffU));
}

/**
 * @brief Compares the two #qe_double values being pointed to and returns
 * true if they are equal.
 * 
 * @param v1: (not nullable) a pointer to a #qe_double key
 * @param v2: (not nullable) a pointer to a #qe_double key to compare with @v1
 *
 * It can be passed to qe_hashtab_new() as the @key_equal_func
 * parameter, when using non-%NULL pointers to doubles as keys in a
 * #qe_hashtab.
 *
 * @return true if the two keys match.
 */
qe_bool qe_double_equal(qe_const_ptr v1, qe_const_ptr v2)
{
    return *((const qe_double*) v1) == *((const qe_double*) v2);
}

/**
 * @brief Converts a pointer to a #qe_double to a hash value.
 * 
 * @param v: (not nullable) a pointer to a #qe_double key
 *
 * It can be passed to qe_hashtab_new() as the @hash_func parameter,
 * when using non-%NULL pointers to doubles as keys in a #qe_hashtab.
 *
 * @return a hash value corresponding to the key.
 */
qe_uint qe_double_hash(qe_const_ptr v)
{
  /* Same as qe_int64_hash() */
  const qe_u64 *bits = v;

  return (qe_uint) ((*bits >> 32) ^ (*bits & 0xffffffffU));
}

/**
 * @brief Initializes a iterator and associates it with tab
 * 
 * @param iter : an uninitialized iterator
 * @param tab : a hash table
 */
void qe_hashtab_iter_init(qe_hashtab_iter *iter, 
    qe_hashtab *tab)
{
    if (!iter || !tab) {
        qe_error("iter or hashtab null");
        return;
    }

    iter->tab = tab;
    iter->pos = -1;
}

/**
 * @brief Retrieves the hash table and return key/val.
 * 
 * @param[in] iter : iterator
 * @param[out] key : a location to store the key
 * @param[out] val : a location to store the val
 * 
 * @return qe_bool false if end of table
 */
qe_bool qe_hashtab_iter_next(qe_hashtab_iter *iter, 
    qe_ptr *key, qe_ptr *val)
{
    qe_int pos;

    if (!iter) {
        qe_error("iter null");
        return qe_false;
    }

    if (iter->pos >= (qe_int)iter->tab->size) {
        qe_error("iter pos:%d out of range:%u", iter->pos, iter->tab->size);
        return qe_false;
    }

    pos = iter->pos;

    do {
        pos++;
        if (pos >= (qe_int)iter->tab->size) {
            iter->pos = pos;
            return qe_false;
        }
    } while (!HASH_IS_REAL(iter->tab->hashes[pos]));

    if (key != QE_NULL) {
        *key = fetch_kv(iter->tab->keys, pos);
    }

    if (val != QE_NULL) {
        *val = fetch_kv(iter->tab->vals, pos);
    }

    iter->pos = pos;

    return qe_true;
}

qe_hashtab *qe_hashtab_iter_get_hashtab(qe_hashtab_iter *iter)
{
    if (!iter) {
        qe_error("iter null");
        return QE_NULL;
    }
    return iter->tab;
}

